/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;


/**
 * <p>
 * 充实横向指针，该树是完全二叉树
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月14日
 */
public class PopulatingNextRightPointersInEachNode {
    
    public void connect(TreeLinkNode root) {
        TreeLinkNode curLevel = root;
        while(curLevel!=null){
            TreeLinkNode across = curLevel;
            while(across!=null){
                //先把左右子树连接起来
                if(across.left!=null){
                    across.left.next = across.right;
                }
                //连接同一层的下一个兄弟
                if(across.right!=null && across.next!=null){
                    across.right.next = across.next.left;
                }
                //在同一层向右走一步
                across = across.next;
            }
            //转到下一层
            curLevel = curLevel.left;
        }
    }
}
